洛谷题解 P3952 【时间复杂度】

发表于 | 更新于 | 阅读次数：
本文字数： 5.5k | 阅读时长 ≈ 5 分钟

思路：

这是一道模拟题，看了一下数据量，纯模拟可以过，按题意来看：

ERR的情况：F与E不匹配和变量名冲突的

No的情况：只有时间复杂度计算错误的

Yes的情况：除以上两种情况外的

其实还有隐藏的条件：

  • 1.F x 1 1 为O(1)

  • 2.F x 1 n 为O(n)

  • 3.F x 32 n 为O(n)

  • 4.F x n 1 为O(1) 且此语句不执行，因为n远大于100

  • 5.并列的For语句复杂度取最高次项值

  • 6.F x n n 为O(1)

  • 5.F x 8 2 为O(1) 且此语句不执行，因为8大于2

  • 6.不执行的语句若下面嵌套了新的For语句也要扫描下去，以防出现ERR的情况

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
char o[1000]={0};//存当前读入的复杂度
int n,nowl,data[500],ans=0;//data存用了的变量及其值
bool erk=false,erp=false;//erk判断是否少了E，erp判断变量重复

void read(int r)
{
    int nd=0,rd=0,pdlt=0;//nd 目前n的次数，rd目前循环数
    bool pdl=false,pdk[1000];//pdl后面嵌套的for语句是否无效，pdk记录第几次循环n的次数+1
    memset(pdk,false,sizeof(pdk));
    char bl[1000]={0};//存变量名
    for(int b=1;b<=r;b++)
    {
        char g;
        string x,y;
        cin>>g;
        if(g=='F')
        {
        	int j=0,k=0,m=0,n=0;
        	rd++;
            cin>>bl[rd];
            if(data[(int)bl[rd]]!=0)
            {
                erp=true;
            }
            cin>>x>>y;
            if(pdl==true)
            {
                continue;
            }
            if(x[0]>='0'&&x[0]<='9')
            {
                while(x[0+j]>='0'&&x[0+j]<='9')
                {
                    k=k*10+x[0+j]-48;
                    j++;
                }
                data[(int)bl[rd]]=k;
            }
            else
            {
                if(x[0]==n)
                {
                    data[(int)bl[rd]]=100;
                }
                else
                {
                    data[(int)bl[rd]]=data[(int)x[0]];
                }
            }
            if(y[0]>='0'&&y[0]<='9')
            {
                while(y[0+m]>='0'&&y[0+m]<='9')
                {
                    n=n*10+y[0+m]-48;
                    m++;
                }
                if(data[(int)bl[rd]]>n)
                {
                    if(pdl==false)
                    {
                        pdlt=rd;
                    }
                    pdl=true;
                }
            }
            else
            {
                if(data[(int)bl[rd]]>data[(int)y[0]])
                {
                    if(pdl==false)
                    {
                        pdlt=rd;
                    }
                    pdl=true;
                }
            }
            if(y[0]=='n'&&x[0]!='n')
            {
                nd++;
                ans=max(nd,ans);
                pdk[rd]=true;
            }
        }
        if(g=='E')
        {
            if(rd<0)
            {     
                erp=true;
            }
            else
            {
            	data[(int)bl[rd]]=0;
                if(pdlt==rd)
                {
                    pdl=false;
                    pdlt=0;
                }
                if(pdk[rd]==true)
                {
                    nd--;
                    pdk[rd]=false;
                }
                rd--;
            }
        }
    }
    if(rd!=0)
    {
        erk=true;
    }
    else
    {
        erk=false;
    }
}

int main()
{
    cin>>n;
    for(int a=1;a<=n;a++)
    {
    	erp=false;
    	bool er=false;
        memset(data,0,sizeof(data));
        ans=0;
        erk=false;
        data[(int)'n']=100;
        bool pd=false;//判断读入复杂度是否为O(n^m)类型
        int fzd=0,ld=0;///fzd读入的复杂度的数字部分
        scanf("%d",&nowl);
        if(nowl%2!=0)
        {           
            er=true;
        }
        scanf("%c",&o[0]);
        while(o[ld]!='\n')
        {
        	ld++;
        	scanf("%c",&o[ld]);
        }
        if(o[3]=='n')
        {
            int t=0;
            pd=true;
            while(o[5+t]>='0'&&o[5+t]<='9')
            {
                fzd=fzd*10+o[5+t]-48;
                t++;
            }
        }
        else
        {
            fzd=1;
        }
        read(nowl);
        if(er==true||erk==true||erp==true)
        {
        	cout<<"ERR"<<endl;
        	continue;
        }
        if(ans==0)
        {
            if(fzd==1)
            {
            	if(pd==true)
            	{
            		cout<<"No"<<endl;
            	}
                else
                {
                	cout<<"Yes"<<endl;
                }
            }
            else
            {
                cout<<"No"<<endl;
            }
            continue;
        }
        if(ans>0)
        {
            if(fzd==ans)
            {
                cout<<"Yes"<<endl;
            }
            else
            {
                cout<<"No"<<endl;
            }
            continue;
        }
    }
}

题目详见:https://www.luogu.org/problemnew/show/P3952